from typing import *


class Solution:

    def combinationSum2(self, candidates: List[int],
                        target: int) -> List[List[int]]:
        cnd = [(v, s) for v, s in Counter(candidates).items()]
        ans = []

        def g(arr):
            ans = []
            for v,s in arr:
                for _ in range(s):
                    ans.append(v)
            return ans

        def f(idx, arr, tot):
            if tot > target:
                return
            if idx == len(cnd):
                if tot == target:
                    ans.append(g(arr))
                return

            f(idx + 1, arr, tot)
            v, s = cnd[idx]
            for i in range(1, s + 1):
                arr.append((v, i))
                f(idx + 1, arr, tot + v * i)
                arr.pop()

        f(0, [], 0)
        return ans